package 力扣.双指针;

public class 环形链表II_142 {
    public ListNode detectCycle(ListNode head) {
//        if (head == null || head.next == null) {
//            return null;
//        }
       ListNode dummy = new ListNode();//使用假头不需要判断链表是否为空
       dummy.next = head;


       ListNode fast = dummy;
       ListNode slow = dummy;
       while (fast != null && fast.next != null){
               fast = fast.next.next;
               slow = slow.next;
               if (fast == slow){//第一次相遇
                   break;
               }
       }
       if (slow != fast){
           return null;
       }
        slow = dummy;//从哪里开始就要从哪里开始:如果起始的是head,则这里也是head
        while (slow != fast){//第二次相遇
            fast = fast.next;
            slow = slow.next;
        }
       return fast;
    }
    public ListNode detectCycle2(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }

        ListNode s1 = head;
        ListNode s2 = head;

        while (s2 != null && s2.next != null) {
            s1 = s1.next;
            s2 = s2.next.next;
            if (s1 == s2) {
                break;
            }
        }

        if (s1 != s2) {
            return null;
        }

        s2 = head;
        while (s1 != s2) {
            s1 = s1.next;
            s2 = s2.next;
        }

        return s1;
    }







    public ListNode detectCycle3(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                break;
            }
        }
        if (fast == null || fast.next == null){
            return null;
        }
        slow = head;
        while (slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}
